STL map随机读取效率测试

背景：map是STL中的重要关联容器，可以根据key值来进行有序插入、随机读取。

map的随机读取很特殊：可以通过中括号访问。 比如map<int,int>sample中有一个元素为pair<4,6>，则可以通过sample[4]的形式访问到这个元素

但由于map为用AVL树存储的关联容器，而不是顺序容器，它的随机读取效率应该只有O(logn),下面进行验证。

下列测试比较了以int和string类型作key值时，插入与随机读取效率。

测试代码：

#include<iostream>
#include<map>
#include<string>
#include<ctime>
#include<iomanip>
using namespace std;

const int length_of_str = 5;//字符串长度

map<string,int>StringMap;
map<int,int>IntMap;

void InsertString(string &str)
{
    StringMap.insert(pair<string,int>(str,1));
    return;
}
void InsertInt(int num)
{
    IntMap.insert(pair<int,int>(num,1));
    return;
}

int main()
{
    string base = "hfauiehlkesadolaijeqpjioehfuoaiyeufhesufhuiesaueiry77861423yeyadhasd73y2ade43derduisadhwuduahdjsdkajhdygyegskfdjskfaugeyrkhdagydgeygyegf";
    string s[100];//存储100个随机字符串
    int nums[100];//存储100个随机数
    for(int i = 0; i < 100; ++i)
    {
        s[i] = base.substr(i,length_of_str);
        nums[i] = (i*762921372)%1000;
    }
    clock_t StartTime, EndTime;
    StartTime = clock(); 
    for(int i = 0; i < 100; ++i)
    {
        for(int i = 0; i < 100; ++i)
        {
            InsertString(s[i]);
        }
    }
    EndTime = clock();
    cout << "string插入时间" << setprecision(3) << setiosflags(ios::fixed)<<(double)EndTime - StartTime << endl;



    StartTime = clock(); 
    for(int i = 0; i < 100; ++i)
    {
        for(int i = 0; i < 100; ++i)
        {
            InsertInt(nums[i]);
        }
    }
    EndTime = clock();
    cout <<"int插入时间"<< setprecision(3) << setiosflags(ios::fixed)<<(double)EndTime - StartTime << endl;


        StartTime = clock(); 
    for(int i = 0; i < 100; ++i)
    {
        for(int i = 0; i < 100; ++i)
        {
            int j = StringMap[s[i]];
        }
    }
    EndTime = clock();
    cout <<"map:string读取时间"<< setprecision(3) << setiosflags(ios::fixed)<<(double)EndTime - StartTime << endl;


    StartTime = clock(); 
    for(int i = 0; i < 100; ++i)
    {
        for(int i = 0; i < 100; ++i)
        {
            int j = IntMap[nums[i]];
        }
    }
    EndTime = clock();
    cout <<"map:Int读取时间"<< setprecision(3) << setiosflags(ios::fixed)<<(double)EndTime - StartTime << endl;


    StartTime = clock(); 
    for(int i = 0; i < 100; ++i)
    {
        for(int i = 0; i < 100; ++i)
        {
            int j = nums[i];
        }
    }
    EndTime = clock();
    cout <<"顺序存储:Int读取时间"<< setprecision(3) << setiosflags(ios::fixed)<<(double)EndTime - StartTime << endl;


    return 0;
}

程序运行结果：

string插入时间72.000
int插入时间23.000
map:string读取时间30.000
map:Int读取时间12.000
顺序存储:Int读取时间0.000

可以发现，map的随机存取与插入的时间复杂度大致是在同一级复杂度（O(logn)），在使用map的下标访问功能时，应考虑操作的时间代价。